#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from collections import defaultdict
from dfa import *
from collections.abc import Iterable


class NFA:
    # 非确定状态机
    def __init__(self, transfer_table, start_state, end_states):
        self.tf    = transfer_table
        self.start = start_state
        self.accepts  = end_states

        self.alphabeta = {'0', '1'}
        self.cur = start_state

    def convert_to_fsm(self, state_prefix):
        # 非确定状态机转确定性状态机.
        tuple_start = (self.start,)
        powerset_tt = TransferTable([])
        queue = [ tuple_start ]

        # visited = set()
        concise_map = {}
        power_accepts = set()
        concise_idx = 0

        while queue:
            big_tuple_state = queue.pop()

            # if big_tuple_state in visited:
            if big_tuple_state in concise_map:
                continue

            # visited.add(big_tuple_state)
            concise_map[big_tuple_state] = state_prefix + str(concise_idx)
            concise_idx += 1

            if self.accepts.intersection(big_tuple_state):
                power_accepts.add(big_tuple_state)

            for c in self.alphabeta:
                new_big_tuple_state = self.transfer_to_results(big_tuple_state, c)
                queue.append(new_big_tuple_state)
                powerset_tt.add(big_tuple_state, c, new_big_tuple_state)

        # 将powerset_tt中的big_tuple_state映射到 新的状态, 新状态使用convert_prefix
        # return powerset_tt
        # states = powerset_tt.states()
        # assert len(states) < 10
        # print(concise_map)

        # return states
        concise_tt = self.get_concise_tt(powerset_tt, concise_map)
        concise_accpets = self.get_concise_ends(power_accepts, concise_map)
        # print("origin :", powerset_tt.tm)
        # print("origin states :", powerset_tt.states())
        # print("map  :", concise_map)
        return DFA(concise_tt, concise_map[tuple_start], concise_accpets)

    def transfer_to_results(self, big_tuple_state, c):
        results = set()

        # print('big and c:', big_tuple_state, c)

        for state in big_tuple_state:
            one_dest_set = self.tf.find(state, c)
            # print('one set', one_dest_set)
            if not one_dest_set:
                continue

            # NOTE: WARNING: str is not Iterable!!!
            if isinstance(one_dest_set, str):
                results.add(one_dest_set)
            elif isinstance(one_dest_set, Iterable):
                results = results.union(one_dest_set)
            else:
                results.add(one_dest_set)

        # print('result', results)
        # print()

        return tuple(results)

    def get_concise_tt(self, powerset_tt, concise_map):
        concise_tt = TransferTable([])

        states = powerset_tt.states()
        # print("state == :", states)
        for big in states:
            for c in self.alphabeta:
                to = powerset_tt.find(big, c)
                cur = concise_map[big]
                dest = concise_map[to]
                assert cur
                assert dest
                concise_tt.add(cur, c, dest)

        return concise_tt

    def get_concise_ends(self, powerset_ends, concise_map):
        concise_accpets = set()

        for e in powerset_ends:
            concise_accpets.add( concise_map[e] )

        return concise_accpets
